<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.4.0">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/Frog_32px_1177822_easyicon.net.ico">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/Frog_32px_1177822_easyicon.net.ico">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/Frog_16px_1177822_easyicon.net.ico">
  <link rel="mask-icon" href="/images/Frog_32px_1177822_easyicon.net.ico" color="#222">

<link rel="stylesheet" href="/css/main.css">


<link rel="stylesheet" href="/lib/font-awesome/css/all.min.css">
  <link rel="stylesheet" href="/lib/pace/pace-theme-minimal.min.css">
  <script src="/lib/pace/pace.min.js"></script>

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"hxy1997.xyz","root":"/","scheme":"Pisces","version":"7.8.0","exturl":false,"sidebar":{"position":"left","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":true,"pangu":false,"comments":{"style":"tabs","active":"valine","storage":true,"lazyload":true,"nav":null,"activeClass":"valine"},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"输入关键字","hits_empty":"没有找到与「${query}」相关搜索","hits_stats":"${hits} 条相关记录，共耗时 ${time} ms"}},"localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.json"};
  </script>

  <meta name="description" content="按照算法和数据结构进行分类，一起来刷题，用于自己在面试前查漏补缺。我的意向岗位是前端，选择用javascript来刷题，优点是动态语言，语法简单，缺点是遇见复杂数据结构会出现较难的写法，如堆、并查集，每题对应leetcode的题号。本篇是数学计算">
<meta property="og:type" content="article">
<meta property="og:title" content="数学计算刷题">
<meta property="og:url" content="https://hxy1997.xyz/2021/03/09/%E6%95%B0%E5%AD%A6%E8%AE%A1%E7%AE%97%E5%88%B7%E9%A2%98/index.html">
<meta property="og:site_name" content="hxy的博客">
<meta property="og:description" content="按照算法和数据结构进行分类，一起来刷题，用于自己在面试前查漏补缺。我的意向岗位是前端，选择用javascript来刷题，优点是动态语言，语法简单，缺点是遇见复杂数据结构会出现较难的写法，如堆、并查集，每题对应leetcode的题号。本篇是数学计算">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210529113439.jpeg">
<meta property="article:published_time" content="2021-03-08T16:02:39.000Z">
<meta property="article:modified_time" content="2021-07-31T06:18:45.373Z">
<meta property="article:author" content="hxy">
<meta property="article:tag" content="javascript">
<meta property="article:tag" content="数据结构和算法">
<meta property="article:tag" content="数学计算">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210529113439.jpeg">

<link rel="canonical" href="https://hxy1997.xyz/2021/03/09/%E6%95%B0%E5%AD%A6%E8%AE%A1%E7%AE%97%E5%88%B7%E9%A2%98/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>数学计算刷题 | hxy的博客</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

<link rel="alternate" href="/atom.xml" title="hxy的博客" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">hxy的博客</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
      <p class="site-subtitle" itemprop="description">Mia san Mia!</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div id="search-result">
  <div id="no-result">
    <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
  </div>
</div>

    </div>
  </div>

</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>
  <div class="reading-progress-bar"></div>

  <a href="https://github.com/huxingyi1997" class="github-corner" title="Follow me on GitHub" aria-label="Follow me on GitHub" rel="noopener" target="_blank"><svg width="80" height="80" viewBox="0 0 250 250" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path></svg></a>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://hxy1997.xyz/2021/03/09/%E6%95%B0%E5%AD%A6%E8%AE%A1%E7%AE%97%E5%88%B7%E9%A2%98/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/Robben.gif">
      <meta itemprop="name" content="hxy">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="hxy的博客">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          数学计算刷题
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              <time title="创建时间：2021-03-09 00:02:39" itemprop="dateCreated datePublished" datetime="2021-03-09T00:02:39+08:00">2021-03-09</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2021-07-31 14:18:45" itemprop="dateModified" datetime="2021-07-31T14:18:45+08:00">2021-07-31</time>
              </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-folder"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/%E5%88%B7%E9%A2%98/" itemprop="url" rel="index"><span itemprop="name">刷题</span></a>
                </span>
            </span>

          
            <span class="post-meta-item" title="热度" id="busuanzi_container_page_pv" style="display: none;">
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              <span class="post-meta-item-text">热度：</span>
              <span id="busuanzi_value_page_pv"></span>
            </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/2021/03/09/%E6%95%B0%E5%AD%A6%E8%AE%A1%E7%AE%97%E5%88%B7%E9%A2%98/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/2021/03/09/%E6%95%B0%E5%AD%A6%E8%AE%A1%E7%AE%97%E5%88%B7%E9%A2%98/" itemprop="commentCount"></span>
    </a>
  </span>
  
  

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <p>按照算法和数据结构进行分类，一起来刷题，用于自己在面试前查漏补缺。我的意向岗位是前端，选择用javascript来刷题，优点是动态语言，语法简单，缺点是遇见复杂数据结构会出现较难的写法，如堆、并查集，每题对应leetcode的题号。本篇是数学计算</p>
<span id="more"></span>

<h2 id="专题部分"><a href="#专题部分" class="headerlink" title="专题部分"></a>专题部分</h2><h3 id="数学计算"><a href="#数学计算" class="headerlink" title="数学计算"></a>数学计算</h3><h4 id="7-整数反转"><a href="#7-整数反转" class="headerlink" title="7. 整数反转"></a>7. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/reverse-integer/">整数反转</a></h4><p>给你一个 32 位的有符号整数 <code>x</code> ，返回将 <code>x</code> 中的数字部分反转后的结果。</p>
<p>如果反转后整数超过 32 位的有符号整数的范围 [−$$ 2^{31} $$ , $$ 2^{31} − 1$$] ，就返回 0。</p>
<p><strong>假设环境不允许存储 64 位整数（有符号或无符号）。</strong></p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：x &#x3D; 123</span><br><span class="line">输出：321</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：x &#x3D; -123</span><br><span class="line">输出：-321</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：x &#x3D; 120</span><br><span class="line">输出：21</span><br></pre></td></tr></table></figure>

<p><strong>示例 4：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：x &#x3D; 0</span><br><span class="line">输出：0</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li>$- 2^{31} &lt;= x &lt;= 2^{31} - 1$</li>
</ul>
<p>不用字符串了，话说小学QB编程就有种题了，需要注意取值范围超过范围值为0</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">x</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> reverse = <span class="function"><span class="keyword">function</span>(<span class="params">x</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (x === <span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="comment">// 正负标志位</span></span><br><span class="line">    <span class="keyword">let</span> sign = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span> (x &lt; <span class="number">0</span>) &#123;</span><br><span class="line">        sign = -<span class="number">1</span>;</span><br><span class="line">        x = -x;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">let</span> xr = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span> (x) &#123;</span><br><span class="line">        xr *= <span class="number">10</span>;</span><br><span class="line">        xr += x % <span class="number">10</span>;</span><br><span class="line">        x = <span class="built_in">Math</span>.floor(x / <span class="number">10</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (xr &gt;= <span class="built_in">Math</span>.pow(<span class="number">2</span>, <span class="number">31</span>)) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">return</span> sign * xr;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="12-整数转罗马数字"><a href="#12-整数转罗马数字" class="headerlink" title="12. 整数转罗马数字"></a>12. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/integer-to-roman/">整数转罗马数字</a></h4><p>罗马数字包含以下七种字符： <code>I</code>， <code>V</code>， <code>X</code>， <code>L</code>，<code>C</code>，<code>D</code> 和 <code>M</code>。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">字符          数值</span><br><span class="line">I             1</span><br><span class="line">V             5</span><br><span class="line">X             10</span><br><span class="line">L             50</span><br><span class="line">C             100</span><br><span class="line">D             500</span><br><span class="line">M             1000</span><br></pre></td></tr></table></figure>

<p>例如， 罗马数字 2 写做 <code>II</code> ，即为两个并列的 1。12 写做 <code>XII</code> ，即为 <code>X</code> + <code>II</code> 。 27 写做 <code>XXVII</code>, 即为 <code>XX</code> + <code>V</code> + <code>II</code> 。</p>
<p>通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 <code>IIII</code>，而是 <code>IV</code>。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 <code>IX</code>。这个特殊的规则只适用于以下六种情况：</p>
<ul>
<li><code>I</code> 可以放在 <code>V</code> (5) 和 <code>X</code> (10) 的左边，来表示 4 和 9。</li>
<li><code>X</code> 可以放在 <code>L</code> (50) 和 <code>C</code> (100) 的左边，来表示 40 和 90。 </li>
<li><code>C</code> 可以放在 <code>D</code> (500) 和 <code>M</code> (1000) 的左边，来表示 400 和 900。</li>
</ul>
<p>给你一个整数，将其转为罗马数字。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: num &#x3D; 3</span><br><span class="line">输出: &quot;III&quot;</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: num &#x3D; 4</span><br><span class="line">输出: &quot;IV&quot;</span><br></pre></td></tr></table></figure>

<p><strong>示例 3:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: num &#x3D; 9</span><br><span class="line">输出: &quot;IX&quot;</span><br></pre></td></tr></table></figure>

<p><strong>示例 4:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入: num &#x3D; 58</span><br><span class="line">输出: &quot;LVIII&quot;</span><br><span class="line">解释: L &#x3D; 50, V &#x3D; 5, III &#x3D; 3.</span><br></pre></td></tr></table></figure>

<p><strong>示例 5:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入: num &#x3D; 1994</span><br><span class="line">输出: &quot;MCMXCIV&quot;</span><br><span class="line">解释: M &#x3D; 1000, CM &#x3D; 900, XC &#x3D; 90, IV &#x3D; 4.</span><br></pre></td></tr></table></figure>

<p> <strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= num &lt;= 3999</code></li>
</ul>
<p>暴力+哈希，找出千位百位十位个位的表达方法，进行对应位的表达</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">num</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;string&#125;</span></span></span></span><br><span class="line"><span class="comment"> * 暴力法，找出千位百位十位个位的表达方法</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> intToRoman = <span class="function"><span class="keyword">function</span>(<span class="params">num</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> M = [<span class="string">&quot;&quot;</span>, <span class="string">&quot;M&quot;</span>, <span class="string">&quot;MM&quot;</span>, <span class="string">&quot;MMM&quot;</span>]; <span class="comment">// 千位</span></span><br><span class="line">    <span class="keyword">const</span> C = [<span class="string">&quot;&quot;</span>, <span class="string">&quot;C&quot;</span>, <span class="string">&quot;CC&quot;</span>, <span class="string">&quot;CCC&quot;</span>, <span class="string">&quot;CD&quot;</span>, <span class="string">&quot;D&quot;</span>, <span class="string">&quot;DC&quot;</span>, <span class="string">&quot;DCC&quot;</span>, <span class="string">&quot;DCCC&quot;</span>, <span class="string">&quot;CM&quot;</span>]; <span class="comment">// 百位</span></span><br><span class="line">    <span class="keyword">const</span> X = [<span class="string">&quot;&quot;</span>, <span class="string">&quot;X&quot;</span>, <span class="string">&quot;XX&quot;</span>, <span class="string">&quot;XXX&quot;</span>, <span class="string">&quot;XL&quot;</span>, <span class="string">&quot;L&quot;</span>, <span class="string">&quot;LX&quot;</span>, <span class="string">&quot;LXX&quot;</span>, <span class="string">&quot;LXXX&quot;</span>, <span class="string">&quot;XC&quot;</span>]; <span class="comment">// 十位</span></span><br><span class="line">    <span class="keyword">const</span> I = [<span class="string">&quot;&quot;</span>, <span class="string">&quot;I&quot;</span>, <span class="string">&quot;II&quot;</span>, <span class="string">&quot;III&quot;</span>, <span class="string">&quot;IV&quot;</span>, <span class="string">&quot;V&quot;</span>, <span class="string">&quot;VI&quot;</span>, <span class="string">&quot;VII&quot;</span>, <span class="string">&quot;VIII&quot;</span>, <span class="string">&quot;IX&quot;</span>]; <span class="comment">// 个位</span></span><br><span class="line">    <span class="keyword">return</span> M[<span class="built_in">Math</span>.floor(num / <span class="number">1000</span>)] + C[<span class="built_in">Math</span>.floor((num % <span class="number">1000</span>) / <span class="number">100</span>)] + X[<span class="built_in">Math</span>.floor((num % <span class="number">100</span>) / <span class="number">10</span>)] + I[num % <span class="number">10</span>];</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="13-罗马数字转整数"><a href="#13-罗马数字转整数" class="headerlink" title="13. 罗马数字转整数"></a>13. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/roman-to-integer/">罗马数字转整数</a></h4><p>罗马数字包含以下七种字符: <code>I</code>， <code>V</code>， <code>X</code>， <code>L</code>，<code>C</code>，<code>D</code> 和 <code>M</code>。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">字符          数值</span><br><span class="line">I             1</span><br><span class="line">V             5</span><br><span class="line">X             10</span><br><span class="line">L             50</span><br><span class="line">C             100</span><br><span class="line">D             500</span><br><span class="line">M             1000</span><br></pre></td></tr></table></figure>

<p>例如， 罗马数字 2 写做 <code>II</code> ，即为两个并列的 1。12 写做 <code>XII</code> ，即为 <code>X</code> + <code>II</code> 。 27 写做 <code>XXVII</code>, 即为 <code>XX</code> + <code>V</code> + <code>II</code> 。</p>
<p>通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 <code>IIII</code>，而是 <code>IV</code>。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 <code>IX</code>。这个特殊的规则只适用于以下六种情况：</p>
<ul>
<li><code>I</code> 可以放在 <code>V</code> (5) 和 <code>X</code> (10) 的左边，来表示 4 和 9。</li>
<li><code>X</code> 可以放在 <code>L</code> (50) 和 <code>C</code> (100) 的左边，来表示 40 和 90。 </li>
<li><code>C</code> 可以放在 <code>D</code> (500) 和 <code>M</code> (1000) 的左边，来表示 400 和 900。</li>
</ul>
<p>给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: &quot;III&quot;</span><br><span class="line">输出: 3</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: &quot;IV&quot;</span><br><span class="line">输出: 4</span><br></pre></td></tr></table></figure>

<p><strong>示例 3:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: &quot;IX&quot;</span><br><span class="line">输出: 9</span><br></pre></td></tr></table></figure>

<p><strong>示例 4:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入: &quot;LVIII&quot;</span><br><span class="line">输出: 58</span><br><span class="line">解释: L &#x3D; 50, V&#x3D; 5, III &#x3D; 3.</span><br></pre></td></tr></table></figure>

<p><strong>示例 5:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入: &quot;MCMXCIV&quot;</span><br><span class="line">输出: 1994</span><br><span class="line">解释: M &#x3D; 1000, CM &#x3D; 900, XC &#x3D; 90, IV &#x3D; 4.</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= s.length &lt;= 15</code></li>
<li><code>s</code> 仅含字符 <code>(&#39;I&#39;, &#39;V&#39;, &#39;X&#39;, &#39;L&#39;, &#39;C&#39;, &#39;D&#39;, &#39;M&#39;)</code></li>
<li>题目数据保证 <code>s</code> 是一个有效的罗马数字，且表示整数在范围 <code>[1, 3999]</code> 内</li>
<li>题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。</li>
<li>IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。</li>
<li>关于罗马数字的详尽书写规则，可以参考 <a target="_blank" rel="noopener" href="https://b2b.partcommunity.com/community/knowledge/zh_CN/detail/10753/%E7%BD%97%E9%A9%AC%E6%95%B0%E5%AD%97#knowledge_article">罗马数字 - Mathematics </a>。</li>
</ul>
<p>关键就是根据定义，前一个数比当前数小，减去前一个数，前一个数大于或等于当前数，加上前一个数</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;string&#125;</span> <span class="variable">s</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> romanToInt = <span class="function"><span class="keyword">function</span>(<span class="params">s</span>) </span>&#123;</span><br><span class="line">    <span class="comment">// 索引</span></span><br><span class="line">    <span class="keyword">let</span> map = &#123;</span><br><span class="line">        <span class="string">&#x27;I&#x27;</span>: <span class="number">1</span>,</span><br><span class="line">        <span class="string">&#x27;V&#x27;</span>: <span class="number">5</span>,</span><br><span class="line">        <span class="string">&#x27;X&#x27;</span>: <span class="number">10</span>,</span><br><span class="line">        <span class="string">&#x27;L&#x27;</span>: <span class="number">50</span>,</span><br><span class="line">        <span class="string">&#x27;C&#x27;</span>: <span class="number">100</span>,</span><br><span class="line">        <span class="string">&#x27;D&#x27;</span>: <span class="number">500</span>,</span><br><span class="line">        <span class="string">&#x27;M&#x27;</span>: <span class="number">1000</span></span><br><span class="line">    &#125;;</span><br><span class="line">    <span class="comment">// 结果</span></span><br><span class="line">    <span class="keyword">let</span> res = <span class="number">0</span>;</span><br><span class="line">    <span class="comment">// 前一个数</span></span><br><span class="line">    <span class="keyword">let</span> pre = map[s[<span class="number">0</span>]];</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i = <span class="number">1</span>; i &lt; s.length; i++) &#123;</span><br><span class="line">        <span class="comment">// 当前的数</span></span><br><span class="line">        <span class="keyword">let</span> cur = map[s[i]];</span><br><span class="line">        <span class="keyword">if</span> (pre &lt; cur) &#123;</span><br><span class="line">            <span class="comment">// 前一个数比当前数小，减去前一个数</span></span><br><span class="line">            res -= pre;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">// 前一个数大于或等于当前数，加上前一个数</span></span><br><span class="line">            res += pre;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 当前数的值赋给当前前一个数</span></span><br><span class="line">        pre = cur;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 最后一个数加入结果</span></span><br><span class="line">    res += pre;</span><br><span class="line">    <span class="comment">// 返回结果</span></span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="31-下一个排列"><a href="#31-下一个排列" class="headerlink" title="31. 下一个排列"></a>31. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/next-permutation/">下一个排列</a></h4><p>实现获取 <strong>下一个排列</strong> 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。</p>
<p>如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。</p>
<p>必须**<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95"> 原地 </a>**修改，只允许使用额外常数空间。 </p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：nums &#x3D; [1,2,3]</span><br><span class="line">输出：[1,3,2]</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：nums &#x3D; [3,2,1]</span><br><span class="line">输出：[1,2,3]</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：nums &#x3D; [1,1,5]</span><br><span class="line">输出：[1,5,1]</span><br></pre></td></tr></table></figure>

<p><strong>示例 4：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：nums &#x3D; [1]</span><br><span class="line">输出：[1]</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= nums.length &lt;= 100</code></li>
<li><code>0 &lt;= nums[i] &lt;= 100</code></li>
</ul>
<p>从末尾找到第一队逆序数，交换位置靠前的数和比他略大的数，数字后面的数从小到大排列</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[]&#125;</span> <span class="variable">nums</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;void&#125;</span> </span>Do not return anything, modify nums in-place instead.</span></span><br><span class="line"><span class="comment"> * 从末尾找到第一队逆序数，交换位置靠前的数和比他略大的数，数字后面的数从小到大排列</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> nextPermutation = <span class="function"><span class="keyword">function</span> (<span class="params">nums</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums.length &lt;= <span class="number">1</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">let</span> p2 = nums.length - <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">let</span> p1 = p2 - <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span> (p2 &gt; <span class="number">0</span> &amp;&amp; nums[p1] &gt;= nums[p2]) &#123;</span><br><span class="line">        p2--;</span><br><span class="line">        p1--;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (p2 === <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="comment">// 数字从大打小排列，是最大的数，下一个数从小到大排列</span></span><br><span class="line">        reverse(nums, <span class="number">0</span>);</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        <span class="keyword">while</span> (p2 &lt;= nums.length - <span class="number">1</span> &amp;&amp; nums[p1] &lt; nums[p2]) &#123;</span><br><span class="line">            p2++;</span><br><span class="line">        &#125;</span><br><span class="line">        p2--;</span><br><span class="line">        <span class="comment">// 交换位置靠前的数和比他略大的数</span></span><br><span class="line">        swap(nums, p1, p2);</span><br><span class="line">        <span class="comment">// 换完后的数从小到大排列</span></span><br><span class="line">        reverse(nums, p1 + <span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 交换nums数组p1位置和p2位置</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">swap</span>(<span class="params">nums, p1, p2</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> temp = nums[p2];</span><br><span class="line">    nums[p2] = nums[p1];</span><br><span class="line">    nums[p1] = temp;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// nums数组从第index位置开始反转</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">reverse</span>(<span class="params">nums, index</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> len = nums.length;</span><br><span class="line">    <span class="keyword">if</span> (index === len || index === len - <span class="number">1</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 双指针进行数字的交换</span></span><br><span class="line">    <span class="keyword">let</span> p1 = index;</span><br><span class="line">    <span class="keyword">let</span> p2 = len - <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span> (p1 &lt; p2) &#123;</span><br><span class="line">        swap(nums, p1, p2);</span><br><span class="line">        p1++;</span><br><span class="line">        p2--;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="69-x-的平方根"><a href="#69-x-的平方根" class="headerlink" title="69. x 的平方根"></a>69. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/sqrtx/">x 的平方根</a></h4><p>实现 <code>int sqrt(int x)</code> 函数。</p>
<p>计算并返回 <em>x</em> 的平方根，其中 <em>x</em> 是非负整数。</p>
<p>由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: 4</span><br><span class="line">输出: 2</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">输入: 8</span><br><span class="line">输出: 2</span><br><span class="line">说明: 8 的平方根是 2.82842..., </span><br><span class="line">     由于返回类型是整数，小数部分将被舍去。</span><br></pre></td></tr></table></figure>

<p>牛顿迭代法</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> mySqrt = <span class="function"><span class="keyword">function</span>(<span class="params">x</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> s = x;</span><br><span class="line">    <span class="keyword">while</span> (s * s &gt; x) &#123;</span><br><span class="line">        s = (s + x / s) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> s;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>二分查找</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> mySqrt = <span class="function"><span class="keyword">function</span>(<span class="params">x</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (x === <span class="number">0</span>) <span class="keyword">return</span> x;</span><br><span class="line">    <span class="keyword">let</span> l = <span class="number">1</span>, r = x, mid, sqrt;</span><br><span class="line">    <span class="keyword">while</span> (l &lt;= r) &#123;</span><br><span class="line">        mid = l + ((r - l) &gt;&gt; <span class="number">1</span>);</span><br><span class="line">        sqrt = <span class="built_in">Math</span>.floor(x / mid);</span><br><span class="line">        <span class="keyword">if</span> (sqrt === mid) &#123;</span><br><span class="line">            <span class="keyword">return</span> mid;</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (mid &gt; sqrt) &#123;</span><br><span class="line">            r = mid - <span class="number">1</span>;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            l = mid + <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> r;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="231-2-的幂"><a href="#231-2-的幂" class="headerlink" title="231. 2 的幂"></a>231. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/power-of-two/">2 的幂</a></h4><p>给你一个整数 <code>n</code>，请你判断该整数是否是 2 的幂次方。如果是，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>
<p>如果存在一个整数 <code>x</code> 使得 $n == 2^{x}$ ，则认为 <code>n</code> 是 2 的幂次方。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：n &#x3D; 1</span><br><span class="line">输出：true</span><br><span class="line">解释：2^0 &#x3D; 1</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：n &#x3D; 16</span><br><span class="line">输出：true</span><br><span class="line">解释：2^4 &#x3D; 16</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：n &#x3D; 3</span><br><span class="line">输出：false</span><br></pre></td></tr></table></figure>

<p><strong>示例 4：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：n &#x3D; 4</span><br><span class="line">输出：true</span><br></pre></td></tr></table></figure>

<p><strong>示例 5：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：n &#x3D; 5</span><br><span class="line">输出：false</span><br></pre></td></tr></table></figure>

<p> <strong>提示：</strong></p>
<ul>
<li>$-2^{31} &lt;= n &lt;= 2^{31} - 1$</li>
</ul>
<p><strong>进阶：</strong>你能够不使用循环/递归解决此问题吗？</p>
<p>位运算，取反之后位与是自身</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">n</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;boolean&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> isPowerOfTwo = <span class="function"><span class="keyword">function</span>(<span class="params">n</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">return</span> n &gt; <span class="number">0</span> &amp;&amp; (n &amp; (-n)) === n;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>位运算，与减一后位与结果为0</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">n</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;boolean&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> isPowerOfTwo = <span class="function"><span class="keyword">function</span>(<span class="params">n</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">return</span> n &gt; <span class="number">0</span> &amp;&amp; (n &amp; (n - <span class="number">1</span>)) === <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>递归</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">n</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;boolean&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> isPowerOfTwo = <span class="function"><span class="keyword">function</span>(<span class="params">n</span>) </span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (n === <span class="number">1</span>) <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    <span class="keyword">if</span> (n === <span class="number">0</span>) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">Math</span>.ceil(n) !== n) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    <span class="keyword">return</span> isPowerOfTwo(n / <span class="number">2</span>);</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>循环计算</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">n</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;boolean&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> isPowerOfTwo = <span class="function"><span class="keyword">function</span> (<span class="params">n</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">while</span> (n &gt;= <span class="number">2</span>) &#123;</span><br><span class="line">    	n = n / <span class="number">2</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> !!(n === <span class="number">1</span>);</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="260-只出现一次的数字"><a href="#260-只出现一次的数字" class="headerlink" title="260. 只出现一次的数字"></a>260. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/single-number-iii/">只出现一次的数字</a></h4><p>给定一个整数数组 <code>nums</code>，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 <strong>任意顺序</strong> 返回答案。</p>
<p> <strong>进阶：</strong>你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？</p>
<p> <strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：nums &#x3D; [1,2,1,3,2,5]</span><br><span class="line">输出：[3,5]</span><br><span class="line">解释：[5, 3] 也是有效的答案。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：nums &#x3D; [-1,0]</span><br><span class="line">输出：[-1,0]</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：nums &#x3D; [0,1]</span><br><span class="line">输出：[1,0]</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>2 &lt;= nums.length &lt;= 3 * 104</code></li>
<li><code>-231 &lt;= nums[i] &lt;= 231 - 1</code></li>
<li>除两个只出现一次的整数外，<code>nums</code> 中的其他数字都出现两次</li>
</ul>
<p>找到两个数异或结果，根据最低位分别对数据进行抑或操作</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">FindNumsAppearOnce</span>(<span class="params"> array </span>) </span>&#123;</span><br><span class="line">    <span class="comment">// 抑或结果</span></span><br><span class="line">    <span class="keyword">let</span> xor_result = <span class="number">0</span>;</span><br><span class="line">    <span class="comment">// 长度</span></span><br><span class="line">    <span class="keyword">const</span> n = array.length;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">        xor_result ^= array[i];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 除了最后1位1，全部置零</span></span><br><span class="line">    <span class="keyword">let</span> flag = xor_result &amp; (-xor_result);</span><br><span class="line">    <span class="comment">// 有无标志位</span></span><br><span class="line">    <span class="keyword">let</span> has_flag = <span class="number">0</span>, hasnot_flag = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (array[i] &amp; flag) &#123;</span><br><span class="line">            <span class="comment">// 标志位为1的抑或结果</span></span><br><span class="line">            has_flag ^= array[i];</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">// 标志位为0的抑或结果</span></span><br><span class="line">            hasnot_flag ^= array[i];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (has_flag &lt; hasnot_flag) &#123;</span><br><span class="line">        <span class="keyword">return</span> [has_flag, hasnot_flag];</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        <span class="keyword">return</span> [hasnot_flag, has_flag];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="338-比特位计数"><a href="#338-比特位计数" class="headerlink" title="338. 比特位计数"></a>338. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/counting-bits/">比特位计数</a></h4><p>给定一个非负整数 <strong>num</strong>。对于 <strong>0 ≤ i ≤ num</strong> 范围中的每个数字 <strong>i</strong> ，计算其二进制数中的 1 的数目并将它们作为数组返回。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: 2</span><br><span class="line">输出: [0,1,1]</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: 5</span><br><span class="line">输出: [0,1,1,2,1,2]</span><br></pre></td></tr></table></figure>

<p><strong>进阶:</strong></p>
<ul>
<li>给出时间复杂度为<strong>O(n*sizeof(integer))**的解答非常容易。但你可以在线性时间</strong>O(n)**内用一趟扫描做到吗？</li>
<li>要求算法的空间复杂度为**O(n)**。</li>
<li>你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 <strong>__builtin_popcount</strong>）来执行此操作。</li>
</ul>
<p>一个一个计算</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">num</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number[]&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> countBits = <span class="function"><span class="keyword">function</span>(<span class="params">num</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> result = [<span class="number">0</span>];</span><br><span class="line">    <span class="keyword">let</span> n = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(n &lt;= num)&#123;</span><br><span class="line">        <span class="keyword">let</span> count = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">let</span> tmpN = n;</span><br><span class="line">        <span class="keyword">while</span>(tmpN !== <span class="number">0</span>)&#123;</span><br><span class="line">            count++;</span><br><span class="line">            tmpN &amp;= (tmpN - <span class="number">1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        result.push(count);</span><br><span class="line">        n++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> result;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>类似动态规划的方案</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">num</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number[]&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> countBits = <span class="function"><span class="keyword">function</span>(<span class="params">num</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> number = [<span class="number">0</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">1</span>; i &lt;= num; i++)</span><br><span class="line">        number[i] = number[i &gt;&gt; <span class="number">1</span>] + (i &amp; <span class="number">1</span>);</span><br><span class="line">        <span class="comment">// 等价于dp[i] = dp[i &amp; (i - 1)] + 1;</span></span><br><span class="line">    <span class="keyword">return</span> number;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="342-4的幂"><a href="#342-4的幂" class="headerlink" title="342. 4的幂"></a>342. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/power-of-four/">4的幂</a></h4><p>给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>
<p>整数 <code>n</code> 是 4 的幂次方需满足：存在整数 <code>x</code> 使得 $n == 4^{x}$</p>
<p> <strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：n &#x3D; 16</span><br><span class="line">输出：true</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：n &#x3D; 5</span><br><span class="line">输出：false</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：n &#x3D; 1</span><br><span class="line">输出：true</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li>$-2^{31} &lt;= n &lt;= 2^{31}- 1$</li>
</ul>
<p><strong>进阶：</strong></p>
<ul>
<li>你能不使用循环或者递归来完成本题吗？</li>
</ul>
<p>如果 n 是 4 的幂，那么 n 的二进制表示中有且仅有一个 1，并且这个 1 出现在从低位开始的第偶数个二进制位上（这是因为这个 1 后面必须有偶数个 0）。这里我们规定最低位为第 0 位，例如 n=16 时，n 的二进制表示为$(10000)_2$<br>唯一的 1 出现在第 4 个二进制位上，因此 n 是 4 的幂。</p>
<p>由于题目保证了 n 是一个 32 位的有符号整数，因此我们可以构造一个整数 $\textit{mask}$，它的所有偶数二进制位都是 0，所有奇数二进制位都是 1。这样一来，我们将 n 和 $\textit{mask}$  进行按位与运算，如果结果为 0，说明 n 二进制表示中的 1 出现在偶数的位置，否则说明其出现在奇数的位置。</p>
<p>根据上面的思路，$\textit{mask}$  的二进制表示为：</p>
<p>$$<br>\textit{mask} = (10101010101010101010101010101010)_2<br>$$</p>
<p>我们也可以将其表示成 16 进制的形式，使其更加美观：</p>
<p>$$<br>\textit{mask} = (\text{AAAAAAAA})_{16}<br>$$</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">num</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;boolean&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> isPowerOfFour = <span class="function"><span class="keyword">function</span>(<span class="params">num</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">return</span> (num &gt; <span class="number">0</span>) &amp;&amp; (!(num &amp; (num - <span class="number">1</span>))) &amp;&amp; ((num &amp; <span class="number">0xaaaaaaaa</span>) == <span class="number">0</span>);</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>如果 n 是 4 的幂，那么它可以表示成$4^{x}$  的形式，我们可以发现它除以 3 的余数一定为 1，即：<br>$$<br>4^x \equiv (3+1)^x \equiv 1^x \equiv 1 \quad (\bmod ~3)<br>$$<br>如果 n 是 2 的幂却不是 4 的幂，那么它可以表示成 $4^x \times 2$ 的形式，此时它除以 3 的余数一定为 2。</p>
<p>因此我们可以通过 n 除以 3 的余数是否为 1 来判断 n 是否是 4 的幂。</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">num</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;boolean&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> isPowerOfFour = <span class="function"><span class="keyword">function</span>(<span class="params">num</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">return</span> (num &gt; <span class="number">0</span>) &amp;&amp; (!(num &amp; (num - <span class="number">1</span>))) &amp;&amp; num % <span class="number">3</span> === <span class="number">1</span>;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="461-汉明距离"><a href="#461-汉明距离" class="headerlink" title="461. 汉明距离"></a>461. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/hamming-distance/">汉明距离</a></h4><p>两个整数之间的<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E6%B1%89%E6%98%8E%E8%B7%9D%E7%A6%BB">汉明距离</a>指的是这两个数字对应二进制位不同的位置的数目。</p>
<p>给出两个整数 <code>x</code> 和 <code>y</code>，计算它们之间的汉明距离。</p>
<p><strong>注意：</strong><br>$0 ≤ x, y &lt; 2^{31}$.</p>
<p><strong>示例:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">输入: x &#x3D; 1, y &#x3D; 4</span><br><span class="line">输出: 2</span><br><span class="line"></span><br><span class="line">解释:</span><br><span class="line">1   (0 0 0 1)</span><br><span class="line">4   (0 1 0 0)</span><br><span class="line">       ↑   ↑</span><br><span class="line"></span><br><span class="line">上面的箭头指出了对应二进制位不同的位置。</span><br></pre></td></tr></table></figure>

<p>将两数异或的结果进行统计1的计数</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">x</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">y</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> hammingDistance = <span class="function"><span class="keyword">function</span>(<span class="params">x, y</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> diff = x ^ y, ans = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span> (diff) &#123;</span><br><span class="line">        ans += diff &amp; <span class="number">1</span>;</span><br><span class="line">        diff &gt;&gt;= <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> ans;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>简化统计1的方式</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">x</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">y</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> hammingDistance = <span class="function"><span class="keyword">function</span>(<span class="params">x, y</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> n = x ^ y;</span><br><span class="line">    <span class="keyword">let</span> res = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span> (n) &#123;</span><br><span class="line">        res++;</span><br><span class="line">        n = n &amp; (n - <span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="477-汉明距离总和"><a href="#477-汉明距离总和" class="headerlink" title="477. 汉明距离总和"></a>477. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/total-hamming-distance/">汉明距离总和</a></h4><p>两个整数的 <a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E6%B1%89%E6%98%8E%E8%B7%9D%E7%A6%BB/475174?fr=aladdin">汉明距离</a> 指的是这两个数字的二进制数对应位不同的数量。</p>
<p>计算一个数组中，任意两个数之间汉明距离的总和。</p>
<p><strong>示例:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">输入: 4, 14, 2</span><br><span class="line">输出: 6</span><br><span class="line"></span><br><span class="line">解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。（这样表示是为了体现后四位之间关系）</span><br><span class="line">所以答案为：</span><br><span class="line">HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) &#x3D; 2 + 2 + 2 &#x3D; 6.</span><br></pre></td></tr></table></figure>

<p><strong>注意:</strong></p>
<ol>
<li>数组中元素的范围为从 <code>0</code>到 <code>10^9</code>。</li>
<li>数组的长度不超过 <code>10^4</code>。</li>
</ol>
<p>统计每一位1的个数</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[]&#125;</span> <span class="variable">nums</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> totalHammingDistance = <span class="function"><span class="keyword">function</span> (<span class="params">nums</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> res = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">const</span> len = nums.length;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; <span class="number">32</span>; i++) &#123;</span><br><span class="line">        <span class="comment">// 左移，mask第i位为1</span></span><br><span class="line">        <span class="keyword">let</span> mask = <span class="number">1</span> &lt;&lt; i;</span><br><span class="line">        <span class="keyword">let</span> count = <span class="number">0</span>;</span><br><span class="line">        <span class="comment">// 统计所有数组元素第i位1的个数</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> value <span class="keyword">of</span> nums) &#123;</span><br><span class="line">            <span class="keyword">if</span> (value &amp; mask) count++;</span><br><span class="line">        &#125;</span><br><span class="line">        res += count * (len - count);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="483-最小好进制"><a href="#483-最小好进制" class="headerlink" title="483. 最小好进制"></a>483. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/smallest-good-base/">最小好进制</a></h4><p>对于给定的整数 n, 如果n的k（k&gt;=2）进制数的所有数位全为1，则称 k（k&gt;=2）是 n 的一个**<em>好进制**</em>。</p>
<p>以字符串的形式给出 n, 以字符串的形式返回 n 的最小好进制。</p>
<p> <strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：&quot;13&quot;</span><br><span class="line">输出：&quot;3&quot;</span><br><span class="line">解释：13 的 3 进制是 111。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：&quot;4681&quot;</span><br><span class="line">输出：&quot;8&quot;</span><br><span class="line">解释：4681 的 8 进制是 11111。</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：&quot;1000000000000000000&quot;</span><br><span class="line">输出：&quot;999999999999999999&quot;</span><br><span class="line">解释：1000000000000000000 的 999999999999999999 进制是 11。</span><br></pre></td></tr></table></figure>

<p> <strong>提示：</strong></p>
<ol>
<li><p>n的取值范围是 [3, 10^18]。</p>
</li>
<li><p>输入总是有效且没有前导 0,</p>
<p>数学方法计算，选择二分查找增加速度</p>
</li>
</ol>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;string&#125;</span> <span class="variable">n</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;string&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> smallestGoodBase = <span class="function"><span class="keyword">function</span>(<span class="params">n</span>) </span>&#123;</span><br><span class="line">    n = BigInt(n);</span><br><span class="line">    <span class="comment">// 先确定 a 的最大值，因为Math.log2的参数不能是 BigInt，所以只能从小到大去算a的 i 次方</span></span><br><span class="line">    <span class="keyword">let</span> a_max;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">1</span>; ; i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (<span class="built_in">Math</span>.pow(<span class="number">2</span>, i) &gt; n) &#123;</span><br><span class="line">            a_max = BigInt(i) + <span class="number">1n</span>;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// console.log(&quot;a_max:&quot; + a_max);</span></span><br><span class="line">    <span class="comment">// a 不能等于 1，因为 a 等于 1 的时候，k 就等于 n 了。但是任意给定一个 n，都可以存在k 等于 n-1，a 等于 2，使得题目成立</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> a = a_max; a &gt;= <span class="number">2n</span>; a--) &#123;</span><br><span class="line">        <span class="comment">// k &gt;= 2 &amp;&amp; k &lt;= n - 1, 可以使用二分查找的方式</span></span><br><span class="line">        <span class="keyword">let</span> start = <span class="number">2n</span>;</span><br><span class="line">        <span class="keyword">let</span> end = n - <span class="number">1n</span>;</span><br><span class="line">        <span class="keyword">let</span> k;</span><br><span class="line">        <span class="keyword">while</span> (<span class="literal">true</span>) &#123;</span><br><span class="line">            k = (start + end) / <span class="number">2n</span>;</span><br><span class="line">            <span class="keyword">let</span> result = (k ** a - <span class="number">1n</span>) / (k - <span class="number">1n</span>);</span><br><span class="line">            <span class="keyword">if</span> (result === n) &#123;</span><br><span class="line">                <span class="keyword">return</span> k.toString();</span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (result &gt; n) &#123;</span><br><span class="line">                end = k - <span class="number">1n</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (result &lt; n) &#123;</span><br><span class="line">                start = k + <span class="number">1n</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (start &gt; end) <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="523-连续的子数组和"><a href="#523-连续的子数组和" class="headerlink" title="523. 连续的子数组和"></a>523. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/continuous-subarray-sum/">连续的子数组和</a></h4><p>给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：</p>
<ul>
<li>子数组大小 <strong>至少为 2</strong> ，且</li>
<li>子数组元素总和为 <code>k</code> 的倍数。</li>
</ul>
<p>如果存在，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>
<p>如果存在一个整数 <code>n</code> ，令整数 <code>x</code> 符合 <code>x = n * k</code> ，则称 <code>x</code> 是 <code>k</code> 的一个倍数。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：nums &#x3D; [23,2,4,6,7], k &#x3D; 6</span><br><span class="line">输出：true</span><br><span class="line">解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">输入：nums &#x3D; [23,2,6,4,7], k &#x3D; 6</span><br><span class="line">输出：true</span><br><span class="line">解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。 </span><br><span class="line">42 是 6 的倍数，因为 42 &#x3D; 7 * 6 且 7 是一个整数。</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：nums &#x3D; [23,2,6,4,7], k &#x3D; 13</span><br><span class="line">输出：false </span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= nums.length &lt;= 105</code></li>
<li><code>0 &lt;= nums[i] &lt;= 109</code></li>
<li><code>0 &lt;= sum(nums[i]) &lt;= 231 - 1</code></li>
<li><code>1 &lt;= k &lt;= 231 - 1</code></li>
</ul>
<p>前缀和+哈希表</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[]&#125;</span> <span class="variable">nums</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">k</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;boolean&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> checkSubarraySum = <span class="function"><span class="keyword">function</span>(<span class="params">nums, k</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> sumMod = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">let</span> map = <span class="keyword">new</span> <span class="built_in">Map</span>();</span><br><span class="line">    map.set(<span class="number">0</span>, -<span class="number">1</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; nums.length; i++) &#123;</span><br><span class="line">        <span class="keyword">const</span> num = nums[i];</span><br><span class="line">        sumMod = (sumMod + num) % k;</span><br><span class="line">        <span class="keyword">if</span> (map.has(sumMod)) &#123;</span><br><span class="line">            <span class="keyword">if</span> (map.get(sumMod) === <span class="literal">true</span> || (i - map.get(sumMod) &gt; <span class="number">1</span>)) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                map.set(sumMod, <span class="literal">true</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            map.set(sumMod, i);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="633-平方数之和"><a href="#633-平方数之和" class="headerlink" title="633. 平方数之和"></a>633. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/sum-of-square-numbers/">平方数之和</a></h4><p>给定一个非负整数 <code>c</code> ，你要判断是否存在两个整数 <code>a</code> 和 <code>b</code>，使得$a^2 + b^2 = c^2$ 。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：c &#x3D; 5</span><br><span class="line">输出：true</span><br><span class="line">解释：1 * 1 + 2 * 2 &#x3D; 5</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：c &#x3D; 3</span><br><span class="line">输出：false</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：c &#x3D; 4</span><br><span class="line">输出：true</span><br></pre></td></tr></table></figure>

<p><strong>示例 4：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：c &#x3D; 2</span><br><span class="line">输出：true</span><br></pre></td></tr></table></figure>

<p><strong>示例 5：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：c &#x3D; 1</span><br><span class="line">输出：true</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li>$0 &lt;= c &lt;= 2^{31} - 1$</li>
</ul>
<p>双指针</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">c</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;boolean&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> judgeSquareSum = <span class="function"><span class="keyword">function</span>(<span class="params">c</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> start = <span class="number">0</span>, end = <span class="built_in">Math</span>.floor(<span class="built_in">Math</span>.sqrt(c));</span><br><span class="line">    <span class="keyword">while</span> (start &lt;= end) &#123;</span><br><span class="line">        <span class="keyword">let</span> sum = start * start + end * end;</span><br><span class="line">        <span class="keyword">if</span> (sum === c)</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (sum &gt; c)</span><br><span class="line">            end--;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            start++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="810-黑板异或游戏"><a href="#810-黑板异或游戏" class="headerlink" title="810. 黑板异或游戏"></a>810. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/chalkboard-xor-game/">黑板异或游戏</a></h4><p>黑板上写着一个非负整数数组 <code>nums[i]</code> 。Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。 (另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0。）</p>
<p>换种说法就是，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0，这个玩家获胜。</p>
<p>假设两个玩家每步都使用最优解，当且仅当 Alice 获胜时返回 <code>true</code>。</p>
<p><strong>示例：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">输入: nums &#x3D; [1, 1, 2]</span><br><span class="line">输出: false</span><br><span class="line">解释: </span><br><span class="line">Alice 有两个选择: 擦掉数字 1 或 2。</span><br><span class="line">如果擦掉 1, 数组变成 [1, 2]。剩余数字按位异或得到 1 XOR 2 &#x3D; 3。那么 Bob 可以擦掉任意数字，因为 Alice 会成为擦掉最后一个数字的人，她总是会输。</span><br><span class="line">如果 Alice 擦掉 2，那么数组变成[1, 1]。剩余数字按位异或得到 1 XOR 1 &#x3D; 0。Alice 仍然会输掉游戏。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= N &lt;= 1000</code></li>
<li><code>0 &lt;= nums[i] &lt;= 2^16</code></li>
</ul>
<p>有偶数个数或者所有数字异或结果为0必胜，否则必败（拿掉1个数后变成后手必胜的情况）</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[]&#125;</span> <span class="variable">nums</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;boolean&#125;</span></span></span></span><br><span class="line"><span class="comment"> * 有偶数个数或者所有数字异或结果为0必胜，否则必败（拿掉1个数后变成后手必胜的情况）</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> xorGame = <span class="function"><span class="keyword">function</span>(<span class="params">nums</span>) </span>&#123;</span><br><span class="line">    <span class="comment">// 偶数个数</span></span><br><span class="line">    <span class="keyword">if</span> (nums.length % <span class="number">2</span> === <span class="number">0</span>) <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    <span class="comment">// 异或结果</span></span><br><span class="line">    <span class="keyword">let</span> xor = nums.reduce(<span class="function">(<span class="params">prev, next</span>) =&gt;</span> prev ^ next);</span><br><span class="line">    <span class="keyword">return</span> xor === <span class="number">0</span>;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="877-石子游戏"><a href="#877-石子游戏" class="headerlink" title="877. 石子游戏"></a>877. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/stone-game/">石子游戏</a></h4><p>亚历克斯和李用几堆石子在做游戏。偶数堆石子<strong>排成一行</strong>，每堆都有正整数颗石子 <code>piles[i]</code> 。</p>
<p>游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。</p>
<p>亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。</p>
<p>假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 <code>true</code> ，当李赢得比赛时返回 <code>false</code> 。</p>
<p> <strong>示例：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">输入：[5,3,4,5]</span><br><span class="line">输出：true</span><br><span class="line">解释：</span><br><span class="line">亚历克斯先开始，只能拿前 5 颗或后 5 颗石子 。</span><br><span class="line">假设他取了前 5 颗，这一行就变成了 [3,4,5] 。</span><br><span class="line">如果李拿走前 3 颗，那么剩下的是 [4,5]，亚历克斯拿走后 5 颗赢得 10 分。</span><br><span class="line">如果李拿走后 5 颗，那么剩下的是 [3,4]，亚历克斯拿走后 4 颗赢得 9 分。</span><br><span class="line">这表明，取前 5 颗石子对亚历克斯来说是一个胜利的举动，所以我们返回 true 。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>2 &lt;= piles.length &lt;= 500</code></li>
<li><code>piles.length</code> 是偶数。</li>
<li><code>1 &lt;= piles[i] &lt;= 500</code></li>
<li><code>sum(piles)</code> 是奇数。</li>
</ul>
<p>先看动态规划吧</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[]&#125;</span> <span class="variable">piles</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;boolean&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> stoneGame = <span class="function"><span class="keyword">function</span>(<span class="params">piles</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> n = piles.length;</span><br><span class="line">    <span class="comment">// 初始化 dp 数组</span></span><br><span class="line">    <span class="keyword">let</span> dp = [];</span><br><span class="line">    <span class="comment">// 填入 base case</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; n; i++)&#123;</span><br><span class="line">        dp[i] = <span class="keyword">new</span> <span class="built_in">Array</span>(n).fill(&#123;<span class="attr">fir</span>: <span class="number">0</span>, <span class="attr">sec</span>: <span class="number">0</span>&#125;);</span><br><span class="line">        dp[i][i] = &#123;<span class="attr">fir</span>: piles[i], <span class="attr">sec</span>: <span class="number">0</span>&#125;;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i = n - <span class="number">1</span>; i &gt;= <span class="number">0</span>; i--)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">let</span> j = i + <span class="number">1</span>; j &lt; n; j++) &#123;</span><br><span class="line">            <span class="comment">// 先手选择最左边或最右边的分数</span></span><br><span class="line">            <span class="keyword">let</span> left = piles[i] + dp[i + <span class="number">1</span>][j].sec;</span><br><span class="line">            <span class="keyword">let</span> right = piles[j] + dp[i][j - <span class="number">1</span>].sec;</span><br><span class="line">            <span class="comment">// 套用状态转移方程</span></span><br><span class="line">            <span class="keyword">if</span>(left &gt; right)&#123;</span><br><span class="line">                dp[i][j].fir = left;</span><br><span class="line">                dp[i][j].sec = dp[i + <span class="number">1</span>][j].fir;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                dp[i][j].fir = right;</span><br><span class="line">                dp[i][j].sec = dp[i][j - <span class="number">1</span>].fir;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// console.log(dp);</span></span><br><span class="line">    <span class="keyword">const</span> last = dp[<span class="number">0</span>][n - <span class="number">1</span>];</span><br><span class="line">    <span class="keyword">return</span> last.fir - last.sec &gt; <span class="number">0</span>;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>说白了小学奥数染色问题</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[]&#125;</span> <span class="variable">piles</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;boolean&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> stoneGame = <span class="function"><span class="keyword">function</span>(<span class="params">piles</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="1074-元素和为目标值的子矩阵数量"><a href="#1074-元素和为目标值的子矩阵数量" class="headerlink" title="1074. 元素和为目标值的子矩阵数量"></a>1074. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/number-of-submatrices-that-sum-to-target/">元素和为目标值的子矩阵数量</a></h4><p>给出矩阵 <code>matrix</code> 和目标值 <code>target</code>，返回元素总和等于目标值的非空子矩阵的数量。</p>
<p>子矩阵 <code>x1, y1, x2, y2</code> 是满足 <code>x1 &lt;= x &lt;= x2</code> 且 <code>y1 &lt;= y &lt;= y2</code> 的所有单元 <code>matrix[x][y]</code> 的集合。</p>
<p>如果 <code>(x1, y1, x2, y2)</code> 和 <code>(x1&#39;, y1&#39;, x2&#39;, y2&#39;)</code> 两个子矩阵中部分坐标不同（如：<code>x1 != x1&#39;</code>），那么这两个子矩阵也不同。</p>
<p><strong>示例 1：</strong></p>
<p><img data-src="https://cdn.jsdelivr.net/gh/huxingyi1997/my_img/img/20210529113439.jpeg" alt="img"></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：matrix &#x3D; [[0,1,0],[1,1,1],[0,1,0]], target &#x3D; 0</span><br><span class="line">输出：4</span><br><span class="line">解释：四个只含 0 的 1x1 子矩阵。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：matrix &#x3D; [[1,-1],[-1,1]], target &#x3D; 0</span><br><span class="line">输出：5</span><br><span class="line">解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：matrix &#x3D; [[904]], target &#x3D; 0</span><br><span class="line">输出：0</span><br></pre></td></tr></table></figure>

<p> <em>提示：</em></p>
<ul>
<li><code>1 &lt;= matrix.length &lt;= 100</code></li>
<li><code>1 &lt;= matrix[0].length &lt;= 100</code></li>
<li><code>-1000 &lt;= matrix[i] &lt;= 1000</code></li>
<li><code>-10^8 &lt;= target &lt;= 10^8</code></li>
</ul>
<p>我们枚举子矩阵的上下边界，并计算出该边界内每列的元素和，则原问题转换成了如下一维问题：</p>
<p>给定一个整数数组和一个整数target，计算该数组中子数组和等于target 的子数组个数。</p>
<p>对于每列的元素和sum 的计算，我们在枚举子矩阵上边界 i 时，初始下边界 j 为 i，此时 sum 就是矩阵第 i 行的元素。每次向下延长下边界 j 时，我们可以将矩阵第 j 行的元素累加到 sum 中。</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[][]&#125;</span> <span class="variable">matrix</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">target</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number&#125;</span></span></span></span><br><span class="line"><span class="comment"> * 前缀和+哈希表</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> numSubmatrixSumTarget = <span class="function"><span class="keyword">function</span>(<span class="params">matrix, target</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> res = <span class="number">0</span>;</span><br><span class="line">    <span class="comment">// 行数和列数</span></span><br><span class="line">    <span class="keyword">const</span> m = matrix.length, n = matrix[<span class="number">0</span>].length;</span><br><span class="line">    <span class="comment">// 枚举上边界</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; m; i++) &#123;</span><br><span class="line">        <span class="keyword">const</span> sum = <span class="keyword">new</span> <span class="built_in">Array</span>(n).fill(<span class="number">0</span>);</span><br><span class="line">        <span class="comment">// 枚举下边界</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> j = i; j &lt; m; j++) &#123;</span><br><span class="line">            <span class="comment">// 前缀和</span></span><br><span class="line">            <span class="keyword">const</span> prefixSum = <span class="keyword">new</span> <span class="built_in">Map</span>();</span><br><span class="line">            prefixSum.set(<span class="number">0</span>, <span class="number">1</span>);</span><br><span class="line">            <span class="comment">// 枚举每列</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">let</span> k = <span class="number">0</span>; k &lt; n; k++) &#123;</span><br><span class="line">                <span class="comment">// 更新每列的元素和</span></span><br><span class="line">                sum[k] += matrix[j][k];</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">let</span> pre = <span class="number">0</span>;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">const</span> x <span class="keyword">of</span> sum) &#123;</span><br><span class="line">                pre += x;</span><br><span class="line">                <span class="keyword">if</span> (prefixSum.has(pre - target)) &#123;</span><br><span class="line">                    res += prefixSum.get(pre - target);</span><br><span class="line">                &#125;</span><br><span class="line">                prefixSum.set(pre, (prefixSum.get(pre) || <span class="number">0</span>) + <span class="number">1</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="1310-子数组异或查询"><a href="#1310-子数组异或查询" class="headerlink" title="1310. 子数组异或查询"></a>1310. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/xor-queries-of-a-subarray/">子数组异或查询</a></h4><p>有一个正整数数组 <code>arr</code>，现给你一个对应的查询数组 <code>queries</code>，其中 <code>queries[i] = [Li, Ri]</code>。</p>
<p>对于每个查询 <code>i</code>，请你计算从 <code>Li</code> 到 <code>Ri</code> 的 <strong>XOR</strong> 值（即 <code>arr[Li] **xor** arr[Li+1] **xor** ... **xor** arr[Ri]</code>）作为本次查询的结果。</p>
<p>并返回一个包含给定查询 <code>queries</code> 所有结果的数组。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line">输入：arr &#x3D; [1,3,4,8], queries &#x3D; [[0,1],[1,2],[0,3],[3,3]]</span><br><span class="line">输出：[2,7,14,8] </span><br><span class="line">解释：</span><br><span class="line">数组中元素的二进制表示形式是：</span><br><span class="line">1 &#x3D; 0001 </span><br><span class="line">3 &#x3D; 0011 </span><br><span class="line">4 &#x3D; 0100 </span><br><span class="line">8 &#x3D; 1000 </span><br><span class="line">查询的 XOR 值为：</span><br><span class="line">[0,1] &#x3D; 1 xor 3 &#x3D; 2 </span><br><span class="line">[1,2] &#x3D; 3 xor 4 &#x3D; 7 </span><br><span class="line">[0,3] &#x3D; 1 xor 3 xor 4 xor 8 &#x3D; 14 </span><br><span class="line">[3,3] &#x3D; 8</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：arr &#x3D; [4,8,2,10], queries &#x3D; [[2,3],[1,3],[0,0],[0,3]]</span><br><span class="line">输出：[8,0,4,4]</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= arr.length &lt;= 3 * 10^4</code></li>
<li><code>1 &lt;= arr[i] &lt;= 10^9</code></li>
<li><code>1 &lt;= queries.length &lt;= 3 * 10^4</code></li>
<li><code>queries[i].length == 2</code></li>
<li><code>0 &lt;= queries[i][0] &lt;= queries[i][1] &lt; arr.length</code></li>
</ul>
<p>借用前缀和思路的前缀异或</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[]&#125;</span> <span class="variable">arr</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[][]&#125;</span> <span class="variable">queries</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number[]&#125;</span></span></span></span><br><span class="line"><span class="comment"> * 前缀异或</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> xorQueries = <span class="function"><span class="keyword">function</span>(<span class="params">arr, queries</span>) </span>&#123;</span><br><span class="line">    <span class="comment">// 个数</span></span><br><span class="line">    <span class="keyword">const</span> n = arr.length;</span><br><span class="line">    <span class="comment">// 存储第i个位置前的数的异或结果</span></span><br><span class="line">    <span class="keyword">const</span> xor = <span class="keyword">new</span> <span class="built_in">Array</span>(n + <span class="number">1</span>).fill(<span class="number">0</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">        <span class="comment">// 按照定义计算</span></span><br><span class="line">        xor[i + <span class="number">1</span>] = xor[i] ^ arr[i];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 结果数组</span></span><br><span class="line">    <span class="keyword">let</span> res = [];</span><br><span class="line">    queries.forEach(<span class="function"><span class="params">item</span> =&gt;</span> &#123;</span><br><span class="line">        <span class="comment">// 输出，前面的数异或两次后为0，实现两个位置之间的异或</span></span><br><span class="line">        res.push(xor[item[<span class="number">0</span>]] ^ xor[item[<span class="number">1</span>] + <span class="number">1</span>]);</span><br><span class="line">    &#125;)</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="1486-数组异或操作"><a href="#1486-数组异或操作" class="headerlink" title="1486. 数组异或操作"></a>1486. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/xor-operation-in-an-array/">数组异或操作</a></h4><p>给你两个整数，<code>n</code> 和 <code>start</code> 。</p>
<p>数组 <code>nums</code> 定义为：<code>nums[i] = start + 2*i</code>（下标从 0 开始）且 <code>n == nums.length</code> 。</p>
<p>请返回 <code>nums</code> 中所有元素按位异或（<strong>XOR</strong>）后得到的结果。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">输入：n &#x3D; 5, start &#x3D; 0</span><br><span class="line">输出：8</span><br><span class="line">解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) &#x3D; 8 。</span><br><span class="line">     &quot;^&quot; 为按位异或 XOR 运算符。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：n &#x3D; 4, start &#x3D; 3</span><br><span class="line">输出：8</span><br><span class="line">解释：数组 nums 为 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) &#x3D; 8.</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：n &#x3D; 1, start &#x3D; 7</span><br><span class="line">输出：7</span><br></pre></td></tr></table></figure>

<p><strong>示例 4：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：n &#x3D; 10, start &#x3D; 5</span><br><span class="line">输出：2</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= n &lt;= 1000</code></li>
<li><code>0 &lt;= start &lt;= 1000</code></li>
<li><code>n == nums.length</code></li>
</ul>
<p>模拟法</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">n</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">start</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> xorOperation = <span class="function"><span class="keyword">function</span>(<span class="params">n, start</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (n == <span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">let</span> res = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">        res ^= start + <span class="number">2</span> * i;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>数学方法优化<br>记 ⊕ 为异或运算，异或运算满足以下性质：</p>
<p>1.x⊕x=0；<br>2.x⊕y=y⊕x（交换律）；<br>3.(x⊕y)⊕z=x⊕(y⊕z)（结合律）；<br>4.x⊕y⊕y=x（自反性）；<br>5.∀i∈Z，有 4i⊕(4i+1)⊕(4i+2)⊕(4i+3)=0。<br>在本题中，我们需要计算start⊕(start+2i)⊕(start+4i)⊕⋯⊕(start+2(n−1))。</p>
<p>在本题中，我们需要计算 start⊕(start+2i)⊕(start+4i)⊕⋯⊕(start+2(n−1))。</p>
<p>观察公式可以知道，这些数的奇偶性质相同，因此它们的二进制表示中的最低位或者均为 1，或者均为 0。于是我们可以把参与运算的数的二进制位的最低位提取出来单独处理。当且仅当 start 为奇数，且 n 也为奇数时，结果的二进制位的最低位才为 1。</p>
<p>此时我们可以将公式转化为(s⊕(s+1)⊕(s+2)⊕⋯⊕(s+n−1))×2+e，其中 $s=\lfloor \frac{\textit{start}}{2}]$，e 表示运算结果的最低位。即我们单独处理最低位，而舍去最低位后的数列恰成为一串连续的整数。</p>
<p>这样我们可以描述一个函数sumXor(x)，表示 0⊕1⊕2⊕⋯⊕x。利用异或运算的性质 5，我们可以将计算该函数的复杂度降低到 O(1)，因为以4i 为开头的连续四个整数异或的结果为 0，所以sumXor(x) 可以被表示为：</p>
<p>$$<br>\text{sumXor}(x)= \begin{cases} x,&amp; x=4k,k\in Z\ (x-1) \oplus x,&amp; x=4k+1,k\in Z\ (x-2) \oplus (x-1) \oplus x,&amp; x=4k+2,k\in Z\ (x-3) \oplus (x-2) \oplus (x-1) \oplus x,&amp; x=4k+3,k\in Z\ \end{cases}<br>$$</p>
<p>我们可以进一步化简该式：</p>
<p>$$<br>\text{sumXor}(x)= \begin{cases} x,&amp; x=4k,k\in Z\ 1,&amp; x=4k+1,k\in Z\ x+1,&amp; x=4k+2,k\in Z\ 0,&amp; x=4k+3,k\in Z\ \end{cases}<br>$$</p>
<p>这样最后的结果即可表示为$$(sumXor(s−1)⊕sumXor(s+n−1))×2+e$$。</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">n</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">start</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> xorOperation = <span class="function"><span class="keyword">function</span>(<span class="params">n, start</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> s = start &gt;&gt; <span class="number">1</span>, e = n &amp; start &amp; <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">let</span> ret = sumXor(s - <span class="number">1</span>) ^ sumXor(s + n - <span class="number">1</span>);</span><br><span class="line">    <span class="keyword">return</span> ret &lt;&lt; <span class="number">1</span> | e;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="keyword">const</span> sumXor = <span class="function">(<span class="params">x</span>) =&gt;</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (x % <span class="number">4</span> === <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> x;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (x % <span class="number">4</span> === <span class="number">1</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (x % <span class="number">4</span> === <span class="number">2</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> x + <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="1720-解码异或后的数组"><a href="#1720-解码异或后的数组" class="headerlink" title="1720. 解码异或后的数组"></a>1720. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/decode-xored-array/">解码异或后的数组</a></h4><p><strong>未知</strong> 整数数组 <code>arr</code> 由 <code>n</code> 个非负整数组成。</p>
<p>经编码后变为长度为 <code>n - 1</code> 的另一个整数数组 <code>encoded</code> ，其中 <code>encoded[i] = arr[i] XOR arr[i + 1]</code> 。例如，<code>arr = [1,0,2,1]</code> 经编码后得到 <code>encoded = [1,2,3]</code> 。</p>
<p>给你编码后的数组 <code>encoded</code> 和原数组 <code>arr</code> 的第一个元素 <code>first</code>（<code>arr[0]</code>）。</p>
<p>请解码返回原数组 <code>arr</code> 。可以证明答案存在并且是唯一的。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：encoded &#x3D; [1,2,3], first &#x3D; 1</span><br><span class="line">输出：[1,0,2,1]</span><br><span class="line">解释：若 arr &#x3D; [1,0,2,1] ，那么 first &#x3D; 1 且 encoded &#x3D; [1 XOR 0, 0 XOR 2, 2 XOR 1] &#x3D; [1,2,3]</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：encoded &#x3D; [6,2,7,3], first &#x3D; 4</span><br><span class="line">输出：[4,2,0,7,4]</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>2 &lt;= n &lt;= 104</code></li>
<li><code>encoded.length == n - 1</code></li>
<li><code>0 &lt;= encoded[i] &lt;= 105</code></li>
<li><code>0 &lt;= first &lt;= 105</code></li>
</ul>
<p>位运算</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[]&#125;</span> <span class="variable">encoded</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number&#125;</span> <span class="variable">first</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number[]&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> decode = <span class="function"><span class="keyword">function</span>(<span class="params">encoded, first</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> res = [first];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; encoded.length; i++) &#123;</span><br><span class="line">        res.push(encoded[i] ^ res[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="1734-解码异或后的排列"><a href="#1734-解码异或后的排列" class="headerlink" title="1734. 解码异或后的排列"></a>1734. <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/decode-xored-permutation/">解码异或后的排列</a></h4><p>给你一个整数数组 <code>perm</code> ，它是前 <code>n</code> 个正整数的排列，且 <code>n</code> 是个 <strong>奇数</strong> 。</p>
<p>它被加密成另一个长度为 <code>n - 1</code> 的整数数组 <code>encoded</code> ，满足 <code>encoded[i] = perm[i] XOR perm[i + 1]</code> 。比方说，如果 <code>perm = [1,3,2]</code> ，那么 <code>encoded = [2,1]</code> 。</p>
<p>给你 <code>encoded</code> 数组，请你返回原始数组 <code>perm</code> 。题目保证答案存在且唯一。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入：encoded &#x3D; [3,1]</span><br><span class="line">输出：[1,2,3]</span><br><span class="line">解释：如果 perm &#x3D; [1,2,3] ，那么 encoded &#x3D; [1 XOR 2,2 XOR 3] &#x3D; [3,1]</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：encoded &#x3D; [6,5,4,6]</span><br><span class="line">输出：[2,4,1,5,3]</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>3 &lt;= n &lt; 105</code></li>
<li><code>n</code> 是奇数。</li>
<li><code>encoded.length == n - 1</code></li>
</ul>
<p>利用异或的性质，以及n是个奇数的条件</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;number[]&#125;</span> <span class="variable">encoded</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number[]&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> decode = <span class="function"><span class="keyword">function</span>(<span class="params">encoded</span>) </span>&#123;</span><br><span class="line">    <span class="comment">// 先求出n，是个奇数</span></span><br><span class="line">    <span class="keyword">const</span> n = encoded.length + <span class="number">1</span>;</span><br><span class="line">    <span class="comment">// 求出1-n的异或结果</span></span><br><span class="line">    <span class="keyword">let</span> xor = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</span><br><span class="line">        xor ^= i;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">let</span> perm = <span class="keyword">new</span> <span class="built_in">Array</span>(n).fill(<span class="number">0</span>);</span><br><span class="line">    <span class="comment">// 求出第一个数的值</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">1</span>; i &lt; n; i += <span class="number">2</span>) &#123;</span><br><span class="line">        perm[<span class="number">0</span>] ^= encoded[i];</span><br><span class="line">    &#125;</span><br><span class="line">    perm[<span class="number">0</span>] ^= xor;</span><br><span class="line">    <span class="comment">// 数组中每个数的值</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">1</span>; i &lt; n; i++) &#123;</span><br><span class="line">        perm[i] = perm[i - <span class="number">1</span>] ^ encoded[i - <span class="number">1</span>];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> perm;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>


    </div>

    
    
    
      
<div>
        <div style="text-align:center;color: #ccc;font-size:14px;">-------------本文结束<i class="fa fa-paw"></i>感谢您的阅读-------------</div>
</div>
        

  <div class="followme">
    <p>欢迎关注我的其它发布渠道</p>

    <div class="social-list">

        <div class="social-item">
          <a target="_blank" class="social-link" href="/atom.xml">
            <span class="icon">
              <i class="fa fa-rss"></i>
            </span>

            <span class="label">RSS</span>
          </a>
        </div>
    </div>
  </div>


      <footer class="post-footer">
          <div class="post-tags">
              <a href="/tags/javascript/" rel="tag"><i class="fa fa-tag"></i> javascript</a>
              <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95/" rel="tag"><i class="fa fa-tag"></i> 数据结构和算法</a>
              <a href="/tags/%E6%95%B0%E5%AD%A6%E8%AE%A1%E7%AE%97/" rel="tag"><i class="fa fa-tag"></i> 数学计算</a>
          </div>

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/2021/03/09/%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E5%92%8C%E5%8F%8C%E6%8C%87%E9%92%88%E5%88%B7%E9%A2%98/" rel="prev" title="滑动窗口和双指针刷题">
      <i class="fa fa-chevron-left"></i> 滑动窗口和双指针刷题
    </a></div>
      <div class="post-nav-item">
    <a href="/2021/03/09/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E5%88%B7%E9%A2%98/" rel="next" title="排序算法刷题">
      排序算法刷题 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          
    <div class="comments" id="valine-comments"></div>

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%B8%93%E9%A2%98%E9%83%A8%E5%88%86"><span class="nav-text">专题部分</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%95%B0%E5%AD%A6%E8%AE%A1%E7%AE%97"><span class="nav-text">数学计算</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#7-%E6%95%B4%E6%95%B0%E5%8F%8D%E8%BD%AC"><span class="nav-text">7. 整数反转</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#12-%E6%95%B4%E6%95%B0%E8%BD%AC%E7%BD%97%E9%A9%AC%E6%95%B0%E5%AD%97"><span class="nav-text">12. 整数转罗马数字</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#13-%E7%BD%97%E9%A9%AC%E6%95%B0%E5%AD%97%E8%BD%AC%E6%95%B4%E6%95%B0"><span class="nav-text">13. 罗马数字转整数</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#31-%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%8E%92%E5%88%97"><span class="nav-text">31. 下一个排列</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#69-x-%E7%9A%84%E5%B9%B3%E6%96%B9%E6%A0%B9"><span class="nav-text">69. x 的平方根</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#231-2-%E7%9A%84%E5%B9%82"><span class="nav-text">231. 2 的幂</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#260-%E5%8F%AA%E5%87%BA%E7%8E%B0%E4%B8%80%E6%AC%A1%E7%9A%84%E6%95%B0%E5%AD%97"><span class="nav-text">260. 只出现一次的数字</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#338-%E6%AF%94%E7%89%B9%E4%BD%8D%E8%AE%A1%E6%95%B0"><span class="nav-text">338. 比特位计数</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#342-4%E7%9A%84%E5%B9%82"><span class="nav-text">342. 4的幂</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#461-%E6%B1%89%E6%98%8E%E8%B7%9D%E7%A6%BB"><span class="nav-text">461. 汉明距离</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#477-%E6%B1%89%E6%98%8E%E8%B7%9D%E7%A6%BB%E6%80%BB%E5%92%8C"><span class="nav-text">477. 汉明距离总和</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#483-%E6%9C%80%E5%B0%8F%E5%A5%BD%E8%BF%9B%E5%88%B6"><span class="nav-text">483. 最小好进制</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#523-%E8%BF%9E%E7%BB%AD%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84%E5%92%8C"><span class="nav-text">523. 连续的子数组和</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#633-%E5%B9%B3%E6%96%B9%E6%95%B0%E4%B9%8B%E5%92%8C"><span class="nav-text">633. 平方数之和</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#810-%E9%BB%91%E6%9D%BF%E5%BC%82%E6%88%96%E6%B8%B8%E6%88%8F"><span class="nav-text">810. 黑板异或游戏</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#877-%E7%9F%B3%E5%AD%90%E6%B8%B8%E6%88%8F"><span class="nav-text">877. 石子游戏</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#1074-%E5%85%83%E7%B4%A0%E5%92%8C%E4%B8%BA%E7%9B%AE%E6%A0%87%E5%80%BC%E7%9A%84%E5%AD%90%E7%9F%A9%E9%98%B5%E6%95%B0%E9%87%8F"><span class="nav-text">1074. 元素和为目标值的子矩阵数量</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#1310-%E5%AD%90%E6%95%B0%E7%BB%84%E5%BC%82%E6%88%96%E6%9F%A5%E8%AF%A2"><span class="nav-text">1310. 子数组异或查询</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#1486-%E6%95%B0%E7%BB%84%E5%BC%82%E6%88%96%E6%93%8D%E4%BD%9C"><span class="nav-text">1486. 数组异或操作</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#1720-%E8%A7%A3%E7%A0%81%E5%BC%82%E6%88%96%E5%90%8E%E7%9A%84%E6%95%B0%E7%BB%84"><span class="nav-text">1720. 解码异或后的数组</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#1734-%E8%A7%A3%E7%A0%81%E5%BC%82%E6%88%96%E5%90%8E%E7%9A%84%E6%8E%92%E5%88%97"><span class="nav-text">1734. 解码异或后的排列</span></a></li></ol></li></ol></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="hxy"
      src="/images/Robben.gif">
  <p class="site-author-name" itemprop="name">hxy</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">80</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/categories/">
          
        <span class="site-state-item-count">8</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">120</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
        <a href="https://github.com/huxingyi1997" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;huxingyi1997" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:huxingyi1997@zju.edu.cn" title="E-Mail → mailto:huxingyi1997@zju.edu.cn" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
  </div>



      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-frog"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">hxy</span>
</div>

<div class="theme-info">
  <div class="powered-by"></div>
  <span class="post-count">博客全站共1039.2k字</span>
</div>

        
<div class="busuanzi-count">
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    <span class="post-meta-item" id="busuanzi_container_site_uv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item" id="busuanzi_container_site_pv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>








      </div>
    </footer>
  </div>

  
  <script src="/lib/anime.min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/lozad@1/dist/lozad.min.js"></script>
  <script src="/lib/velocity/velocity.min.js"></script>
  <script src="/lib/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/pisces.js"></script>


<script src="/js/next-boot.js"></script>




  




  
<script src="/js/local-search.js"></script>













  

  


<script>
NexT.utils.loadComments(document.querySelector('#valine-comments'), () => {
  NexT.utils.getScript('//unpkg.com/valine/dist/Valine.min.js', () => {
    var GUEST = ['nick', 'mail', 'link'];
    var guest = 'nick,mail,link';
    guest = guest.split(',').filter(item => {
      return GUEST.includes(item);
    });
    new Valine({
      el         : '#valine-comments',
      verify     : false,
      notify     : true,
      appId      : 'pQsO3ySbU4VtWN2j1FLA74Ha-gzGzoHsz',
      appKey     : 'QYacMDY2VY7Wazprg1X6FiUv',
      placeholder: "Just go go",
      avatar     : 'mm',
      meta       : guest,
      pageSize   : '10' || 10,
      visitor    : false,
      lang       : 'zh-cn' || 'zh-cn',
      path       : location.pathname,
      recordIP   : false,
      serverURLs : ''
    });
  }, window.Valine);
});
</script>

  
  <!-- 动态背景特效 -->
  <!-- 樱花特效 -->
    <script async src="/js/src/sakura.js"></script>
    <script async src="/js/src/fairyDustCursor.js"></script>
</body>
</html>
